00100				August 29, 1972
00200	
00300	Dear Bert:
00400	
00500	There are lots of working documents about LISP70, and  you  may  have
00600	got  hold of some that we distributed privately.  However, we request
00700	that you do not publish any of the material  in  them,  as  they  are
00800	obsolete and emphasize many areas of little importance.
00900	
01000	We  do  not  plan to publish anything about LISP70 until it works. We
01100	are rather annoyed when we read about new systems and  then  discover
01200	that  they  were never really implemented successfully. Nevertheless,
01300	some ideas going into LISP70 are of general interest  and  some  have
01400	been  tested  extensively  in  1.5  years  of experience with MLISP2.
01500	Therefore I am enclosing two short working papers of this type.   The
01600	rest of this letter is a blurb about LISP70 culled from various other
01700	sources and tailored to your purpose.
01800	
01900	LISP70 is based on LISP.  The design  goals,  most  important  first,
02000	are:
02100		(1) Extensibility
02200		(2) Inter-machine transferability
02300		(3) Facilititated Debugging
02400		(4) Convenient input and output
02500		(5) Efficiency of Operation
02600	
02700	At  first  glance,  these  goals seem orthogonal to those of PLANNER,
02800	QA-4, SAIL, etc.   However, extensibility  includes  the  ability  do
02900	define  new  control  structures,  and it is achieved by rewrite rule
03000	tables which build pattern-matching and backtracking  into  the  core
03100	language.   The core also includes a variety of data types, extensive
03200	monitoring capabilities, and an MLISP notation.
03300	
03400	Input and output are facilitated by  "streaming".   Any  list,  file,
03500	string,  or  other  "sequence" can be pointed to by a "pointer" which
03600	scans it left to right but can be backed up on failure. Input streams
03700	are  scanned by "source pointers" and output streams are generated by
03800	"destination  pointers".   Intrinsic  functions  move  the  pointers,
03900	extracting  or  inserting  data as the case may be.  These intrinsics
04000	are called implicitly by rewrite rules, which are the  basis  of  the
04100	pattern  matcher.   Thus,  the  matcher can stream from core to core,
04200	core to file, file to core, or file to file, depending on the targets
04300	of  the source and destination pointers.  In particular, file to file
04400	operations such as compilation avoid  nearly  all  cons'es  by  using
04500	streaming.
04600	
04700	Efficiency  is  achieved  in  the pattern matcher by grouping rewrite
04800	rules into tables.  Each table is called  an  "extendable  function",
04900	because  new  rules may be added to it at any time, and the rules may
05000	be applied by use of a  function  call.   Tables  are  compiled,  not
05100	interpreted.  During  compilation, factoring of common parts of rules
05200	and hashing of atomic elements  is  performed  to  attain  processing
05300	speeds comparable to precedence-type compilers.  Backtracking in most
05400	cases is instantaneous because of detection of special  cases  during
05500	compilation.  Complex backtracking is made fairly rapid by techniques
05600	discussed in one of the enclosed papers.
05700	
05800	The first version of LISP70  does  not  use  the  "staging  area"  or
05900	"activation record" control structure mechanism described by numerous
06000	authors during the last ten years.  To woo users away from  LISP  and
06100	SAIL,  we  are  keeping  a  multi-stack structure for now so they can
06200	maintain  their  accustomed  efficiency  with  existing   programming
06300	styles.     Multiple    processes   are   implemented   by   separate
06400	non-hierarchial stacks; the specification  of  inter-process  control
06500	conventions  is extensible.  Activation record control structure will
06600	be added later as an optional mode for those  who  have  a  need  for
06700	hierarchial processes.
06800	
06900	Important differences from the "other" languages:
07000	
07100	Patterns  are compiled, not interpreted; ordered automatically by the
07200	compiler according to definite but  extensible  rules,  not  randomly
07300	ordered;  able  to  process  streams  to avoid most cons'ing; able to
07400	parse strings as well as decompose lists.
07500	
07600	Backtracking is automatic but "fast"; tree search can be  "suspended"
07700	to achieve occasional breadth-first search; multiple processes can be
07800	used alternatively to search goal trees.
07900	
08000	The language is truly extensible: data types can be created not  only
08100	by  cartesian product and union but also from scratch; extensions can
08200	be made at the M-notation level, at  the  S-notation  level,  at  the
08300	idealized LISP machine level.
08400	
08500	The language is machine-independent but can take advantage of special
08600	facilities of individual machines by adding special rewrite rules  to
08700	any program.
08800	
08900	A  single  implementation  will run on several machines, except for a
09000	small  machine-dependent  portion.   The   implementations   can   be
09100	generated and maintained at a central location.
09200	
09300	It can be run in compiler-compiler mode to generate systems for other
09400	languages, thus allowing rapid implementation of other languages.
09500	
09600	The interpreter is normally not used.  EVAL calls the compiler,  thus
09700	insuring  consistent  results, allowing extensions to the compiler to
09800	be recognized by EVAL, and permitting EVAL to operate in the  correct
09900	scope  of  lexical  declarations.   Thus,  functions  may be declared
10000	within functions and variables may have lexical scope.  The  compiler
10100	is always around so compilation entails no overhead.
10200	
10300	We  don't  have  paging on our PDP-10.  Instead, we are using dynamic
10400	storage allocation within an expandable/contractable block  of  core,
10500	segmentation,  and relocatable code and data.  Shared code and tables
10600	are in a read-only second segment.
10700	
10800	I  hope  it  is clear that these facilities are useful for artificial
10900	intelligence.   LISP70 should be able to do anything that can be done
11000	in  PLANNER,  QA-4,  or SAIL, and will shine in its own special ways.
11100	The easiest way to approach theorem proving and  planning  in  LISP70
11200	will be different than the easiest way in PLANNER and QA-4, namely by
11300	use of rules of inference  organized  into  groups  corresponding  to
11400	Extendable Functions.
11500	
11600	There are lots more interesting concepts in LISP70  too  numerous  to
11700	describe,  and many implementation clevernesses that are not relevent
11800	to your purpose. Someday we expect to have it working and  produce  a
11900	manual  and  some papers.  The state of implementation is as follows:
12000	most of the system has been completely coded at least once;  most  of
12100	the  language  features  have been compiled successfully; much of the
12200	storage allocation  has  been  tested;  some  object  code  has  been
12300	executed. The backtracking scheme is similar to but an improvement of
12400	that used since early 1971 in MLISP2 (Horace J.  Enea  and  David  C.
12500	Smith).  LISP70 was designed by and is being implemented by Horace J.
12600	Enea, David C. Smith,  and  Lawrence  G.  Tesler.   If  you  need  an
12700	estimated completion date, say "1973", but I'd rather you didn't need
12800	it.
12900	
13000				Sincerely yours,
13100	
13200				Larry Tesler